import java.util.*;

public class Test {
    public static void main(String[] args) {
        
    }
}


class Solution
{
    public int ladderLength(String beginWord, String endWord, List<String>
            wordList)
    {
        Set<String> hash = new HashSet<>();
        for(String s : wordList) hash.add(s);
        Set<String> vis = new HashSet<>(); // 标记已经搜索过的单词
        if(!hash.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        int ret = 1;
        while(!q.isEmpty())
        {
            ret++;
            int sz = q.size();
            while(sz-- != 0)
            {
                String t = q.poll();
                for(int i = 0; i < t.length(); i++)
                {
                    char[] tmp = t.toCharArray();
                    for(char ch = 'a'; ch <= 'z'; ch++)
                    {
                        tmp[i] = ch;
                        String next = new String(tmp);
                        if(hash.contains(next) && !vis.contains(next))
                        {
                            if(next.equals(endWord)) return ret;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
